Content addressable memory (CAM) devices can be a common component of search engine systems. Search engine systems typically perform a search operation that can compare a search value (e.g., a comparand or key) against a number of other data values. In the event a search value matches a data value, a search result may be considered a “hit” (e.g., match). If a search value does not match any data values, a search result may be considered a “miss” (e.g., no match).
A CAM based search engine can typically include one or more CAM devices. A CAM device may include a number of entries, each of which may store a data value, or portion thereof In a search operation, a comparand (or key) may be compared to multiple entries to see if all, or a portion, of the key matches an entry. After a search operation, a CAM device may give a search result as an output. Typically a search result may provide associated data directly, or provide an “index” value that may be used to retrieve associated data from another device, such as a random access memory.
CAM devices may include a CAM array section (or CAM “core”) that can take a various forms. As but a few of the possible examples, a CAM array section may be based on particular types of CAM cells. Such cells may include storage circuits integrated with compare circuits. Examples of storage circuits may be static random access memory (SRAM) type cells or dynamic random access memory (DRAM) type cells. Alternate approaches may include random access memories (RAM) arrays, or the like, with separate matching circuits and/or processing circuits.
Accordingly, a CAM array section may provide various functions, including but not limited to storing various data values for comparison with a search key value, receiving a search key value, and comparing a search key value to stored data values in order to generate match results. In addition, a CAM array section may provide maskable compare operations. In such an arrangement, a CAM array section may store or receive a mask value corresponding to a search key value. Such a mask value can enable selective comparison of search key values to stored data values by masking bits from a compare operation according to a mask value.
A conventional CAM device will now be described.
Referring now to FIG. 9, a conventional CAM device is set forth in a block diagram and designated by the general reference character 900. A conventional CAM device 900 may include a CAM array section 902 that includes a number of CAM entries (ENTRY0 to ENTRYn). Each entry (ENTRY0 to ENTRYn) may store a data value for comparison with an applied key value KEY. A data value stored in an entry (ENTRY0 to ENTRYn) can have a predetermined width, shown as W.
Thus, in a compare operation, a search key value of size W may be compared to data values of size W stored within entries (ENTRY0 to ENTRYn). In such an operation, an entire array can be activated, with each CAM entry consuming power. Further, in conventional ternary CAM operations, CAM entries (ENTRY0 to ENTRYn) can provide bit-wise masking on an entry-by-entry basis. Thus, each CAM entry (FNTRYO to ENTRYn) can be conceptualized as including a data value and a mask value. For example, each conventional ternary CAM entry may include a data value of W bits and a corresponding mask value of W bits.
Examples of a conventional CAM system will now be described.
A conventional CAM system is set forth in FIG. 10 and designated by the general reference character 1000. A conventional CAM system 1000 may include a number of CAM devices (1002-0 to 1002-3) having common connections to a command and data bus 1004, as well as separate common connections to an index or result bus 1006. Optionally, an index or result bus 1006 may be connected to one or more memory devices 1008, such as a static random access memory (SRAM).
In a system like that shown in FIG. 10, a search command may be issued from a host device 1010 on a command and data bus 1004. Such a search command may include a search key of a predetermined size (e.g., W bits). CAM devices (1002-0 to 1002-3) may process such a command by comparing a search key of W bits to data values of a same size (W bits). Search results may be output on an index or result bus 1006. In this way, utilization of CAM devices (1002-0 to 1002-3) can enable compare operations for search keys of size W to be “offloaded” from a processor (e.g., host device 1010) to CAM devices (1002-0 to 1002-3). This may allow for faster or higher throughput search results, as CAM devices (1002-0 to 1002-3) may typically execute such compare operations at a much faster rate than a general purpose processor.
While a search engine system 1000 may provide for rapid compare operations relative to general processor based systems, it may be desirable to provide different or additional features in such a system.
One desirable feature can be searching according to “sub-word” sizes. That is, if CAM entries may store data values of size W, it may be desirable to also offer the ability to compare search keys of a smaller size (e.g., ½W) to data values of a corresponding size. Of course, it is understood that the term “word” is not meant to correspond to a particular bit size, but rather to reflect an entry size of a CAM device.
Sub-word size compare operations may be accomplished in ternary CAM devices by including sub-word mask values. Such an arrangement can be a waste of storage space, however.
Another conventional approach to accommodate sub-word sizes has included offloading such operations to a general purpose processor, or the like (e.g., a host). As but one example, a host may perform a hashing function on smaller search key sizes, to thereby generate an address for associated data. A drawback to utilizing a host for hashing smaller size search values is that such an approach works against overall system performance. As noted above, a search engine system may include CAM devices in order to offload such computing requirements from a host, or the like. Thus, requiring a host to hash smaller size search keys undesirably consumes host resources, which can reduce overall search speeds and/or rates.
Another desirable feature of a search engine system can be range matching. In many applications, such as network applications, it can be desirable to determine if a value in a particular data packet field falls within a predetermined range. In a conventional approach, a small range match could be accommodated by a corresponding range of entries. That is, CAM entries could be programmed with each value in a given range. Unfortunately, for larger ranges such an approach may be impractical, as a range could consume too many entries.
An alternative way of accommodating range matching can include offloading such operations to a host, or the like. An algorithm executed by a host could then extract a desired data field from a packet, and then compare particular packet values to high and low ranges. An indication may then be generated if a value is within a given range. A drawback to such an approach can be the undesirable load placed on a host.
Another way to provide range matching can include a novel CAM device that provides range matching capabilities on a per entry basis. One such approach is disclosed in commonly owned, co-pending U.S. patent application Ser. No. 10/217,746, filed on Aug. 13, 2002, entitled “CONTENT ADDRESSABLE MEMORY (CAM) DEVICE WITH ENTRIES HAVING TERNARY MATCH AND RANGE COMPARE FUNCTIONS” by Richard K. Chou. The contents of this application are incorporated herein.
While per entry range matching may provide desirable capabilities in some applications, in other applications range matching may only represent a smaller portion of all compare operations. Thus, for such applications, per entry range matching may underutilize range matching capabilities.
It is always desirable to arrive at some way of reducing the power consumed by an integrated circuit, such as a CAM device. Various approaches to reducing power consumption in a CAM device have been proposed. One conventional power reduction approach may include comparing a small portion of a data value to a corresponding portion of a search key value. A comparison for a remaining larger portion of a data value may then be conditioned on the compare results of a first portion. While such an approach may provide for some power savings, it may be desirable to realize even more power savings.
It would also be desirable to arrive at some way providing range matching capabilities in a search engine system that does not necessarily rely on per entry range matching.
In light of the above, it would be desirable to arrive at some way providing sub-word matching capabilities in a search engine system that does not undesirable add to computing tasks of a host.